package uf;

/**
 * description:
 * author:张腾
 * date:2021-04-09
 */

/**
 * 并查集
 */
public class UF {
    //记录节点元素和该元素所在分组的标识
    private int[] eleAndGroup;
    //记录并查集中数据的分组个数
    private int count;

    private UF(int N){

        this.count = N;
        this.eleAndGroup = new int[N];
        //初始化eleAndGroup中的元素及其所在组的标识符，让并查集每个节点元素作为eleAndGroup的索引，元素所在的组的标识符作为索引处的值
        for (int i = 0; i < eleAndGroup.length; i++) {
            eleAndGroup[i] = i;
        }
    }

    //获取当前并查集中的数据有多少分组
    public int count(){
        return count;
    }

    //元素p所在的分组的标识符
    public int find(int p){
        return eleAndGroup[p];
    }

    //判断并查集中元素p和元素q是否在同一分组中
    public boolean connected(int p,int q){

        return find(p) == find(q);
    }

    //把p元素所在分组和q元素所在分组合并
    public void union(int p,int q){
        //p,q已经在同一分组内则结束方法
        if (connected(p,q)){
            return;
        }

        int pGroup = find(p);
        int qGroup = find(q);

        //将p所在组的所有元素的组标识符变为q所在组的组标识符
        for (int i = 0; i < eleAndGroup.length; i++) {
            if (eleAndGroup[i] == pGroup){
                eleAndGroup[i] = qGroup;
            }
        }

        //分组个数-1
        count--;
    }
}
